[Day 28] B+ Tree

11th鐵人賽

dennisliuu

2019-10-10 21:10:51

817 瀏覽

分享至

B+ Tree

看完昨天的 B Tree，今天從它的進階版開始：B+ Tree
雖然在 Introdution to alogrithm 3rd 中沒有特別分一個類出來
但它還是蠻有趣的

特徵

在每個葉子節點中，都會有一個指向下一個節點的指針

圖源：https://zh.wikipedia.org/wiki/B%2B%E6%A0%91
由於 B+ 樹的葉子節點間按順序建立了鏈指標，因此使樹看起來更加扁平
並因為有了指標，加強了區間訪問性
同時也使 B+ 樹對索引列上的區間範圍查詢更好更省空間，讓查詢 I/O 變小